package com.kuang.recursion;

/*题目：
    输入n，得到斐波那契数列的第n项
*/


import java.util.HashMap;

/**
 * @author kjx
 */
public class Fibonacci {
    public static HashMap<Integer, Long> temp = new HashMap<>();


    //方法和爬梯子一模一样，这里不再赘述
    public static long getFibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        if (temp.get(n) != null) {
            return temp.get(n);
        } else {
            long num = getFibonacci(n - 1) + getFibonacci(n - 2);
            temp.put(n, num);
            return num;
        }
    }

    public static void main(String[] args) {
        System.out.println(getFibonacci(50));
    }
}
